package com.wdc.binarytree;


import org.junit.Test;

import java.util.LinkedList;

//前序中序遍历不用递归
@SuppressWarnings("all")
public class E01Leetcode144 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, null),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))

        );

        LinkedList<TreeNode> stack = new LinkedList<>();   //建栈 ，用于找到来时的路

        TreeNode curr = root;  //代表当前节点
        while(curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                colorPrintln("来： "+curr.val,31);  //前序代码
                curr = curr.left;
            }else {
                TreeNode pop = stack.pop();
                colorPrintln("回： "+ pop,35);   //中序代码
                curr = pop.right;
            }
        }
        postOder(root);

    }

    private static void colorPrintln(String origin,int color){
        System.out.printf("\033[%dm%s\033[0m%n",color,origin);
    }

    //后序遍历
    public static void postOder(TreeNode root){

        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;  //当前节点
        TreeNode curr = root;
        while ( curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);

                //处理左子树
                curr = curr.left;
            }else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop){
                     pop = stack.pop();
                    System.out.println("回： "+pop);
                }else {

                    //处理右子树
                    curr = peek.right;
                }
            }
        }


    }

    @Test
    public void test(){
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, new TreeNode(7)),
                1,
                new TreeNode(new TreeNode(5), 3, new TreeNode(6))

        );
        postOder(root);

    }



}
